#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int minDistance(char* word1, char* word2);

int main()
{
	return 0;
}

int minDistance(char* word1, char* word2)
{
	int len1 = strlen(word1), len2 = strlen(word2);
	short dp[len1 + 1][len2 + 1];
	memset(dp, 0, sizeof(short));

	for (int idx_p = 1; idx_p <= len2; idx_p++) dp[0][idx_p] = idx_p;
	for (int idx_s = 1; idx_s <= len1; idx_s++) dp[idx_s][0] = idx_s;

	for (int idx_s = 1; idx_s <= len1; idx_s++) {
		for (int idx_p = 1; idx_p <= len2; idx_p++) {
			char ch_s = word1[idx_s - 1], ch_p = word2[idx_p - 1];
			if (ch_p == ch_s)
				dp[idx_s][idx_p] = dp[idx_s - 1][idx_p - 1];
			else
				dp[idx_s][idx_p] = fmin(fmin(dp[idx_s - 1][idx_p], dp[idx_s][idx_p - 1]), dp[idx_s - 1][idx_p - 1]) + 1;
		}
	}

	return dp[len1][len2];
}
